"""
硬币称重问题。

算法：
把硬币均分称两堆，若是奇数，则拿出一个来，再分为两堆。
1. 奇数，两堆质量相等，则轮空的一枚就是所求。若两堆质量不相等，则堆1与轮空比较，
若相等，则硬币就在
"""

# 不正常的硬币过轻或者过重。

# 我们现假设这枚不正常的硬币要么是过轻，要么是过重。
# 这里就以过轻为例子进行求解。


from array import array


def FindCoin(A, left, right):
    n = right-left+1
    if n == 3:
        # left, left+1, right
        if A[right] == A[left+1]:  # left?
            return left
        if A[left] == A[right]:  # left+1?
            return left+1
        return right  # must be right.

    if n % 2 == 0:  # 偶数的情况，分开两遍称重即可。
        mid = (left+right)//2
        # 求和，比较，模拟一次称重。
        left_sum = sum(A[left:mid+1])
        right_sum = sum(A[mid+1:right+1])
        if left_sum < right_sum:  # 左边过轻，问题硬币在左边。
            return FindCoin(A, left, mid)
        else:
            return FindCoin(A, mid+1, right)  # 右边过轻，问题硬币在右边
    else:
        # 化为偶数的情况
        mid = (left+right)//2
        left_sum = sum(A[left:mid])
        right_sum = sum(A[mid+1:right+1])
        if left_sum == right_sum:  # 两边一样重，说明问题硬币是中间那个。
            return mid
        if left_sum < right_sum:
            return FindCoin(A, left, mid-1)
        else:
            return FindCoin(A, mid+1, right)

# 我们再假设不正常的硬币不知道它是过轻还是过重，也就是算法不但要
# 检查出不正常的硬币，还要检查出它是过轻还是过重。


def FindCoin2(A, n):
    # 两两分组称重。
    last = None
    if n % 2 == 1:
        last = n-1
        n -= 1
    abnormal = None
    normal_val = None
    for i in range(0, n, 2):
        if A[i] != A[i+1]:
            abnormal = [i, i+1]
        else:
            normal_val = A[i]

    # 两两分组没检查出异常值，说明轮空的last是异常值。
    if abnormal is None:
        assert last is not None
        return last
    # 如果没有找到正常的值，这说明分组太少了，只有一个异常分组。
    # 而此时必有last是正常的。
    if normal_val is None:
        normal_val = A[last]

    for i in abnormal:
        if A[i] != normal_val:
            return i


NORMAL_COIN = 1
PROBLEM_COIN = 0


def MakeData(n):
    assert n >= 3
    ans: list = [NORMAL_COIN]*n  # 设置正常硬币。
    ans[0] = PROBLEM_COIN  # 设置一个问题硬币（过轻）
    import random
    random.shuffle(ans)  # 问题硬币的位置是随机的。
    pos = ans.index(PROBLEM_COIN)
    return ans, pos


def TestFindCoin():
    for n in range(3, 10):
        for _ in range(10):
            A, pos = MakeData(n)
            ans = FindCoin(A, 0, n-1)
            assert ans == pos, f'n={n}, A={A}, pos={pos}, ans={ans}'


def TestFindCoin2():
    for n in range(3, 10):
        for _ in range(10):
            A, pos = MakeData(n)
            ans = FindCoin2(A, n)
            assert ans == pos, f'n={n}, A={A}, pos={pos}, ans={ans}'


def main():
    A, pos = MakeData(5)
    ans = FindCoin(A, 0, len(A)-1)
    print(A, pos)
    print(ans)


TestFindCoin2()
